package leetcode.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 给你一个 无重复元素 的整数数组candidates 和一个目标整数target，找出candidates中可以使数字和为目标数target 的 所有不同组合 ，
 并以列表形式返回。你可以按 任意顺序 返回这些组合。

 andidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

 */
public class CombinationSum40 {

    public static void main(String[] args) {
        int []  candidates = new int[]{10,1,2,7,6,1,5};
        List<List<Integer>> res = new CombinationSum40().combinationSum2(candidates, 8);
        for (List<Integer> re : res) {
            System.out.println(re);
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> tempList = new LinkedList<>();
        Arrays.sort(candidates);
        combinationSum3(candidates,res,tempList,0,0, target);
        return  res;
    }

    public void combinationSum3(int[] candidates, List<List<Integer>> res, LinkedList<Integer> temList, int index,int cur, int target) {
        if(cur > target){
            return ;
        }

        if(cur==target){
            ArrayList<Integer> temp = new ArrayList<>(temList);
            res.add(temp);
            return;
        }

        for (int i = index; i < candidates.length; i++) {

            if(i>index && candidates[i]==candidates[i-1])//去重
                continue;

            temList.offer(candidates[i]);
            combinationSum3(candidates,res,temList,i+1,cur+candidates[i],target);
            temList.removeLast();//回溯还原状态

        }
    }
}